1. Field of the Invention
The present invention relates to an index structure of metadata provided for searching for information on contents and a method for providing indices of the metadata, and a method and an apparatus for searching for the metadata using the index structure of the metadata. More particularly, the present invention relates to an index structure of metadata provided for searching for information on contents and a method for providing indices of the metadata, and a method and an apparatus for searching for the metadata using the indices of metadata, the metadata containing multi-keys with which information on contents can be more efficiently searched when XML metadata on digital contents defined by TV-Anytime Forum (hereinafter referred to as “TVA metadata”) is divided into fragments as an independent unit and transmitted on a fragment basis. The present application is based on Korean Patent Application Nos. 2002-43097 and 2002-62923, which are incorporated herein by reference.
2. Description of the Related Art
The TV-Anytime Forum is a private standardization organization established in September 1999 with the purpose of developing standards for providing audiovisual related services in a user-friendly environment such as a personal digital recorder (PDR) having a high volume personal storage device. Specifically, the aim of the services is to enable all the users to view and listen to various types of programs (such as conventional broadcasting services, online interactive services and the like) at a desired time and in a desired manner based on the personal storage device.
The TV-Anytime Forum has operated Working Groups for business models, system/transmission interfaces/contents referencing, descriptions, metadata, rights management and protection and the like, in order to establish standardization. With respect to the metadata concerned in the present invention, “1st Draft of Metadata Specification SP003v1.3” up to June 2002 has been published.
A configuration of the PDR will be briefly described with reference to FIG. 1. The PDR 100 receives video/audio signals and metadata via a variety of networks such as sky waves, satellite waves, internet networks and the like from a provider 200 for providing video/audio signals, collects viewing and listening patterns, and personal tastes of users, if necessary, and transmits them to the provider 200 for providing the video/audio signals. The PDR 100 comprises a high volume storage device for storing therein the received video/audio signals and metadata. The PDR 100 further comprises software for storage and reproduction of the video/audio signals, and an electronic program guide (EPG) application for retrieving and displaying metadata for the video/audio signals. The user ascertains the metadata for the video/audio data, i.e., titles of the programs, program reproduction times and the like, through a grid guide screen of the EPG application shown in FIG. 2, selects a desired program, and receives it via the network in real time or reproduces the video/audio data previously stored in the high volume storage device.
The metadata refer to data describing contents such as titles and synopses of programs, and are defined as “data about data.” In the TVA metadata specifications of the TV-Anytime Forum, its structure is defined by use of XML schema language (see XML 1.0 of W3C), the standard by the W3C (a consortium for promoting standards for the XML), and the semantics and attributes of the respective metadata elements are also defined. The TVA metadata relevant to broadcasting contents are configured with an XML document having a root node, “TVAMain (300)” as shown in FIG. 3. The TVA metadata relevant to programs are configured with, for example, nodes such as ProgramInformation Table, GroupInformation Table, ProgramLocation Table, ServiceInformation Table and the like, under the node of “ProgramDescription.”
In the TV-Anytime Forum, the TVA metadata are transmitted on a fragment basis as an independent unit in order to transmit a large volume of TVA metadata in a stream format. The concept of fragments will be briefly described with reference to FIG. 4. The fragments are obtained by dividing the TVA metadata configured with the XML documents shown in FIG. 3 into predetermined tree structures. For example, where the entire TVA metadata are divided into a tree structure (fragment TVAMain) including an upper node of “TVAMain” and predetermined child nodes under this upper node, a tree structure (fragment ProgramInformation) including an upper node of ProgramInformation Table and child nodes under this upper node, a tree structure (fragment BroadcastEvent) including an upper node of the BroadcastEvent Information and child nodes under this upper node, each of the divided tree structures becomes a fragment. The fragments can be transmitted independently of the other fragments, and the fragments can be accessed individually.
For individual access to the fragments, it is necessary to know a node referenced by a transmitted TVA metadata fragment, i.e., a node corresponding to the upper node of the TVA metadata fragment, in the entire metadata tree structure, and to describe relative paths in the TVA metadata fragments of keys contained in the transmitted TVA metadata fragment. To this end, XPath, which is a syntax for describing a path to one or more nodes in an XML document defined by W3C, is used. The term ‘key’ refers to a specific field of the metadata used for indexing, and also means child nodes of a node referenced by a fragment. Fields (for search conditions) input by the user, such as ‘Service ID’ and ‘Published Time’ correspond to the keys.
In order to provide efficient search for and access to fragments, an index structure for the keys included in the metadata fragments is additionally required, and information on the index structure, i.e., index information, is also transmitted independently of the metadata fragments.
Under the environment provided by the TV-Anytime Forum, if a user desires to retrieve information on a program meeting a predetermined Published Time condition, the index information transmitted thereto independently of the fragments is utilized to identify the location (identifier) of a metadata fragment meeting a desired Published Time condition and an access to the relevant metadata fragment is then made based on the location (identifier), so as to extract metadata meeting the Published Time condition.
TV-Anytime Specification TV145, J. P. Evain, “1st Draft of Metadata Specification SP003v1.3”, TV-Anytime Forum 17th meeting, Montreal, Canada, June 2002; hereinafter, referred to as “Single key index art reference” proposes a single key index structure for a metadata fragment index.
Note that the term “single key” is used herein to distinguish it from a concept of the term “multi-key” in an embodiment of the present invention to be described later. A multi-key index structure according to an embodiment of the present invention enables the user to access metadata for a plurality of keys, using a plurality of the keys simultaneously, but a single key index structure of the prior art allows only one single key to be used for an access to the metadata.
The notion of a container defined by the TV-Anytime Forum will be described prior to describing the index structure.
The TV-Anytime Forum defines a container as a top-level storage to which all the data covering the aforementioned index information and the metadata fragments are transmitted, which is called a type of top-level transmission. Describing the container briefly, each container comprises a plurality of sections, each storing therein the index information or the metadata fragments. The container can be classified into an index container and a data container according to the information carried thereby: the index container carries index information sections such as a key index list (key_index_list) section, a key index (key_index) section, a sub key index (sub_key_index) section, a string repository (string_repository) section and a fragment data repository (fragment_data_repository) section, whereas a data container carries metadata fragment sections such as an elements table (elements_table) section, a string repository (string_repository) section and a fragment data repository (fragment_data_repository) section. The above classification is done based on the contents of the information included in the containers. Both the index container and the data container are identical in configuration.
Referring to the container defined by the TV-Anytime Forum as illustrated in FIG. 5, the container comprises a container identifier (container_id) data field (not shown) and a large number of sections. In each section, the contents stored in ‘section_body’ are identified according to an encoded value in ‘section_id’. For example, a section 10 of which the encoded value in ‘section_id’ is ‘0X0004’ is identified as a key index list (key_index_list) section, a section 20 of which the encoded value in ‘section_id’ is ‘0X0005’ is identified as a key index (key_index) section, a section 30 of which the encoded value in ‘section id’ is ‘0X0006’ is identified as a sub key index (sub_key_index) section, a section 40 of which the encoded value in ‘section id’ is ‘0X0001’ is identified as an element table (element_table) section, and a section 50 of which the encoded value in ‘section id’ is ‘0X0003’ is identified as a fragment data repository (fragment_data_repository) section.
The TVA metadata fragments are stored in the fragment data repository (fragment_data_repository) section 50 of the data container and then transmitted. The identifier information (handle_value) for the TVA metadata fragments in the data container is included in the element table section 40 of the data container.
In conclusion, the TVA metadata fragment is uniquely identified by the container identifier information (container_id) and the metadata fragment identifier information (handle_value) of the container that includes the TVA metadata fragment.
The single key index art reference described above proposes the single key index structure for indexing the TVA metadata fragments stored in the aforementioned data container, i.e., a structure composed of the key index list (key_index_list) section 10, the key index (key_index) section 20, and the sub key index (sub_key_index) section 30. Since the syntax of the structure is described in detail in the single key index reference described above, the detailed description thereof will be omitted. Hereinafter, the structure will be described with reference to FIG. 6 that illustrates the structure by segments of the index information.
The key index list (key_index_list) section 10 defined in the single key index structure provides a list of all the single keys transmitted. The list includes single key information defining each single key and identification information on the key index (key_index) section 20 to be described later. The single key information comprises (1) location information of the metadata fragment relevant to the single key, and (2) location information of the single key within the metadata fragment. The location information of the metadata fragment is expressed in XPath (fragment_xpath_ptr) in the TVA. The location information of the single key is expressed in XPath (key_xpath_ptr) for the relative path within the relevant fragment of the node used as the single key in the TVA.
The XPath of the metadata fragment is a path to the root node of the TVA metadata XML document, i.e., an absolute path, and the XPath of the nodes used as the single keys, i.e., the XPath of the single keys, represents a relative path of the single key for the relevant metadata fragment. The XPath for the metadata fragment and the XPath for the single key are stored in a ‘fragment_xpath_ptr’ segment 11 and a ‘key_xpath_ptr’ segment 12, respectively.
Furthermore, the key index list (key_index_list) section 10 includes the identification information on the key index (key_index) section 20 of each single key to be described later (i.e., the container identifier information (container_id) of the container storing therein the key index (key_index) section 20 and the key index identifier information). The container identifier information and the key index identifier information are stored in an ‘index_container’ segment of the key index list (key_index_list) section 10 and a ‘key_index_identifier’ segment, respectively, and then transmitted.
The key index (key_index) section 20 defined in the single key index structure provides a list of information representing the ranges of values of the key included in the respective sub key index (sub_key_index) sections 30, i.e., the highest value of the key among the values of the key within the respective range (hereinafter referred to as a ‘representative key value’), and identification information on the sub key index (sub_key_index) section 30 relevant to each representative key value (i.e., the container identifier information (container_id) of the container storing therein the sub key index (sub_key_index) section, and the sub key index identifier information).
Accordingly, the key index section (key_index) 20 includes a ‘key_index_identifier’ segment for storing therein the key index identifier information defined in the key index list (key_index_list) section 10, ‘high_key_value’ segments 13 for storing therein the representative key values of the respective ranges of values of the key included in the sub key index (sub_key_index) section 30, and ‘sub_index_container’ segments and ‘sub_index_identifier’ segments for the identification information on the sub key index (sub_key_index) section 30 (i.e., for the container identifier information (container_id) of the container in which the sub key index (sub_key_index) section 30 is stored, and the respective sub key index identifier information). The sub key index (sub_key_index) section 30 defined in the single key index structure provides a list of the values of the key. The list further includes identification information on the metadata fragments corresponding to the values of the key (i.e., the container identifier information (container_id) of the containers storing the metadata fragments and the identifier information (handle_value) of the metadata fragments).
Accordingly, the sub key index (sub_key_index) section 30 includes a ‘sub_index_identifier’ segment for storing therein the sub key index identifier information defined in the key index (key_index) section 20, ‘key_value’ segments 14 for storing therein the respective ranges of values of the key, ‘target_container’ segments for storing therein the respective container identifier information (container_id) of the containers in which the metadata fragments are stored, and ‘target_handle’ segments for storing therein the respective fragment data identifier information (handle_value). The single key index structure may be more easily understood by referring to FIG. 7 illustrating the index information.
FIGS. 7a and 7b show the key index list (key_index_list) section including single keys relevant to the Service Id, the Published Time and the Published Duration. The upper node of the metadata fragment including the single keys relevant to the Service Id, the Published Time and the Published Duration is ‘BroadcastEvent’ 310 as shown in FIG. 3, identified by a shaded block. Accordingly, the XPath ‘/TVAMain/ProgramDescription/Program-Location Table/BroadcastEvent’ for the ‘BroadcastEvent’ fragment is stored in the ‘fragment_xpath_ptr’ segment 11a, and the XPaths to the single keys of the Service Id, the Published Time and the Published Duration for the ‘BroadcastEvent’ fragment, i.e., ‘@ServiceId’ (311a in FIG. 3), ‘EventDescription/PublishedTime’ (311b in FIG. 3) and ‘EventDescription/PublishedDuration’ (311c in FIG. 3) are stored in the ‘key_xpath_ptr’ segment 12a. 
Illustratively, FIG. 7a shows a key index (key_index) section 20a and a sub key index (sub_key_index) section 30a for the Service Id (XPath of the single key: @ServiceId) of the key index list (key_index_list) section 10a. FIG. 7b shows a key index (key_index) section 20b and a sub key index (sub_key_index) section 30b for the Published Time (XPath of the single key: EventDescription/PublishedTime).
This single key index structure is disadvantageous in that it is inefficient to perform a compound condition search, i.e., a search by one or more search conditions, since it can only support a single key search, i.e., an index search using a key corresponding to a specific field of the metadata fragment according to the TV-Anytime specification. For example, in order to display a list of broadcast programs on the grid guide screen as shown in FIG. 2, search operations for two fields, i.e., the Service Id and the Published Time, are required.
In order to explain the compound condition search using a conventional single key index structure, a case where a list of programs of which a Service Id is in the range of 507 to 514 and the Published Time for 09:30 to 10:00 will be explained hereinafter by way of example. In the TV-Anytime metadata specification, search conditions for retrieving metadata related to the program list are expressed as follows.                Fragment targeted for search (BroadcastEvent):        
/TVAmain/ProgramDescription/ProgramLocationTable/BroadcastEvent,                List of search conditions:        
507<=ServiceId<=514
09:30<=EventDescription/PublishedTime<=10:00.
In the conventional single key index structure, two methods are available for obtaining fragments meeting the designated search conditions. The methods will be described in detail with reference to FIGS. 8a and 8b. 
(1) First Search Method Using the Single Key Index
In the first method, as shown in FIG. 8a, sets of fragments as intermediate results meeting respective conditions are independently searched by use of respective single keys for the ServiceId and the EventDescription/PublishedTime. Thereafter, fragments common in both sets of the independently searched fragments are obtained, among which a final resultant set of fragments meeting the conditions is obtained.
Hereinafter, this method will be described in detail with reference to FIGS. 7a and 8a. 
First, single key information and the value of the single key required for each of the Service Id search and Published Time search is designated (S11). The single key information comprises XPath of the search target metadata fragment as location information of the search target metadata fragment, and XPath of the single key as location information of the single key within the metadata fragment.
XPath of the metadata fragment:
/TVAMain/ProgramDescription/ProgramLocationTable/BroadcastEvent,
XPath of the Service Id: @ServiceId,
Value of key of the Service Id: 507<=ServiceId<=514.
Subsequently, the single key corresponding to the XPath 11a of the fragment and the XPath 12a of the Service Id is retrieved from a key index list (key_index_list) section 10a, and identification information on a key index (key_index) section 20a is extracted. On this basis, representative key values of ‘509’ 13a and ‘519’ 13a, i.e., representative key values which indicate ranges (500-509, 510-519) of values of the key in which values of the key (507-514) to be searched are included, are retrieved from the key index (key_index) section 20a having the extracted identification information. Then, identification information on sub key index (sub_key_index) section 30a for segments 14a having the respective ranges of values of the key (500-509, 510-519) related to the representative key values ‘509’ and ‘519’ is extracted. The identification information of the metadata fragments (i.e., the container identifier information (container_id) and the fragment data identifier information (handle_value) stored in a ‘target_container’ segment and a ‘target_handle’ segment, respectively) corresponding to the values of key of 507-514 is extracted from the sub key index (sub_key_index) section 30a, and the relevant metadata fragments are extracted by using the extracted identification information (S12, S14).
For searching the Published Time as an example, the single key information, i.e., XPath information of the search target metadata fragment and XPath information of the single key, and the value of the single key are expressed as follows.
XPath of the fragment:
/TVAMain/ProgramDescription/ProgramLocationTable/BroadcastEvent,
XPath of the Published Time: EventDescription/PublishedTime,
Value of the key of the Published Time: 09:30<=EventDescription/PublishedTime<=10:00.
Metadata fragments corresponding to the values of key of 09:30-10:00 are extracted through the substantially same steps as in the Service Id search (S13, S15). The intersection between the extracted metadata fragments for the Service Id and the Published Time is performed, and metadata of common metadata fragments are provided to the grid guide screen shown in FIG. 2 as a final result (S16).
(2) Second Search Method Using the Single Key Index
In the second method, the fragments are searched by use of only one (for example, Service Id) of the two single keys related to the search conditions as illustrated in FIG. 8b (S21-S23), and only the fragments of which the Published Time as another search condition, that is, between 09:30 and 10:00, are selected from the searched fragments (S24).
Since intermediate resultant fragments obtained through the search using the respective single keys is usually very large in number, these search methods using the single key index structure are not efficient. In the first method, since all programs in the range of the relevant Service Id are obtained as a search result independently of the range of the Published Time, and programs in the relevant time range for all the Service Ids are obtained as the search result, the size of the search result may become very large. Moreover, since the calculation is also complicated in the process of combining the two intermediate search results large in size, overhead in the receiving apparatus is considerably increased. In the second method, one intermediate result should be additionally filtered by the other search condition. Consequently, the compound condition search using the single key index structure may cause heavy overhead in the receiving apparatus. Additionally, when a search condition for a single key is input, location information on a field of the search condition in the metadata is determined and the determined location information is compared to key information in the key index list so as to search the corresponding key. In such a case, an overhead is caused since comparison of both XPaths is necessary.